// https://leetcode.cn/problems/find-all-duplicates-in-an-array/

/*
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

// n个数，范围在1，n

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]



*/

// 注意：不能使用额外的空间，且时间复杂度为O(N)
#include <vector>
#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
	// 暴力算法，不可以
    vector<int> findDuplicates(vector<int>& nums) {
		int len = nums.size();
		int left = 0;
		int right = len - 1;
		unordered_set<int> ex;
		vector<int> res;
		while(left < right){
			auto iter = ex.find(nums[left]);
			if(iter == ex.end()){
				ex.insert(nums[left]);
			}else{
				res.push_back(nums[left]);
			}
			iter = ex.find(nums[right]);
			if(iter == ex.end()){
				ex.insert(nums[right]);
			}else{
				res.push_back(nums[right]);
			}
			left++;
			right--;
		}
		if(left == right){
			auto iter = ex.find(nums[left]);
			if(iter == ex.end()){
				ex.insert(nums[left]);
			}else{
				res.push_back(nums[left]);
			}
		}
		return res;
    }
	
	// 先排序，再查找， 但是比上面的方法要快一点
	vector<int> findDuplicates1(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<int> res;
		for(int i = 0; i < nums.size()-1; i++){
			if(nums[i] == nums[i+1]){
				res.push_back(nums[i]);
				i++;
			}
		}
		return res;
	}
	
	// 将值作为下标去访问，如果第一次的话，则对应下标的值变为负数，如果是第二次访问的话发现是负数则代表已经重复
	vector<int> findDuplicates2(vector<int>& nums) {
		vector<int> res;
		for(int i = 0; i < nums.size(); i++){
			int index = abs(nums[i]);
			if(nums[index-1] < 0){
				res.push_back(index);
			}else{
				nums[index-1] = -1 * nums[index-1];
			}
		}
		return res;
	}
};

int main(){
	Solution so;
	vector<int> nums = {1,1};

	vector<int> res = so.findDuplicates2(nums);
	for(auto i : res){
		cout << i << ",";
	}
	cout << endl;
	return 0;
}